package com.tarzan.cms.utils;


import java.util.*;

public class ShortestPath {


    HashMap<String, String> parent;
    HashSet<String> bests;
    int[] distance;

    public ShortestPath(int len){
        parent = new HashMap<>(); // key: 当前节点，value：从原点到达key的最短路径的前驱节点
        distance = new int[len]; // distance[i]: 原节点到节点i的最短距离
        bests = new HashSet<>(); // 选择过的最优的节点的集合
    }

    public void dijkstra(int[][] weights, String[] nodes, int start,int end){
        // 1. 初始化：源点到自身距离为0，到其他节点距离为无穷大
        for(int i=0;i<nodes.length;i++){
            if(i==start-1)
                this.distance[i] = 0;
            else this.distance[i] = Integer.MAX_VALUE;
        }
        // 不断迭代
        while (true){
            int min = Integer.MAX_VALUE;
            int index = -1;
            // 1. 在未标记的节点中找出从源点到该点最短的路径节点
            for(int i=0;i<this.distance.length;i++){
                if(this.distance[i] < min && !bests.contains(nodes[i])){
                    min = this.distance[i];
                    index = i;
                }
            }
            System.out.println("index="+index);
            // 找不到可达的路径了
            if(index == -1){
                break;
            }
            // 将该节点放入bests集合中
            this.bests.add(nodes[index]);
            // 2. 扩展该节点的子节点，计算源点到子节点的距离，若小于原来距离，则更新
            // distance表和parent表
            for(int i=0;i<nodes.length;i++){
                // 找到一个为扩展的子节点
                if(weights[index][i]>0 && !bests.contains(nodes[i])){
                    int new_dis = distance[index] + weights[index][i];
                    // 新距离小于原始距离，更新
                    if(new_dis < distance[i]){
                        distance[i] = new_dis;
                        parent.put(nodes[i], nodes[index]);
                    }
                }
            }
        }
        // 倒叙查找到路径
        if(this.distance[end-1] == Integer.MAX_VALUE){
            System.out.print(nodes[start-1]+"到"+nodes[end-1]+"之间没有最短路径");
        }else {
            ArrayList<String> path = new ArrayList<>();
            String current = nodes[end-1];
            path.add(current);
            while (current != nodes[start-1]){
                current = parent.get(current);
                path.add(current);
            }
            for(int i=path.size()-1;i>=0;i--){
                if(i!=0)
                    System.out.print(path.get(i)+"->");
                else System.out.print(path.get(i));
            }
        }
        System.out.println();
        parent.forEach((k,v)->{
            System.out.println(k+" "+v);
        });
    }

    //假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连
//visit[i] == 0,代表未访问,visit[0] == -1代表已访问
    public int Dijkstra(int src, int dst, int[][] graph,String[] nodes){
        //节点个数
        int n = graph.length;
        int[] visit=new int[n];
        PriorityQueue<Node> pq = new PriorityQueue<>(new Node());
        //将起点加入pq
        pq.add(new Node(src, 0));
        while (!pq.isEmpty()){
            Node t = pq.poll();
            //当前节点是终点，即可返回最短路径
            if(t.node == dst){
                return t.cost;
            }
            System.out.println(t.node+"  "+nodes[t.node]);
            //t节点表示还未访问
            if (visit[t.node]==0){
                //将节点设置为已访问
                visit[t.node] = -1;
                //将当前节点相连且未访问的节点遍历
                for (int i = 0; i < n; i++) {
                    if (graph[t.node][i]!=-1 && visit[i]==0) {
                        pq.add(new Node(i, t.cost + graph[t.node][i]));
                    }
                }
            }
        }
        return -1;
    }
    //定义一个存储节点和离起点相应距离的数据结构
    class Node implements Comparator<Node> {
        public int node;
        public int cost;

        public Node(){}

        public Node(int node, int cost){
            this.node = node;
            this.cost = cost;
        }
        @Override
        public int compare(Node node1, Node node2){
            return node1.cost-node2.cost;
        }
    }
    public static void main(String[] args){
        int[][] weight= {{0,-1,10,-1,30,100},{-1,0,5,-1,-1,-1},{-1,-1,0,50,-1,-1},{-1,-1,-1,0,-1,10},
                {-1,-1,-1,20,0,60},{-1,-1,-1,-1,-1,0}};
        String[] str= {"V1","V2","V3","V4","V5","V6"};
        int len=str.length;
        ShortestPath p1 = new ShortestPath(len);
        p1.dijkstra(weight, str, 1,5);
        p1.Dijkstra(1,6,weight,str);
    }

}
